package likou.jindian;

import java.util.Arrays;

/**
 * @author: Tangxz
 * @email: 1171702529@qq.com
 * @cate: 2020/12/15 08:21
 */
public class _04_10 {
    static boolean p = false;
    static boolean nowP = true;

    public static void main(String[] args) {
//        TreeNode root = new TreeNode(3);
//        root.left = new TreeNode(5);
//        root.right = new TreeNode(1);
//        root.left.left = new TreeNode(6);
//        root.left.right = new TreeNode(2);
//        root.left.right.left = new TreeNode(7);
//        root.left.right.right = new TreeNode(4);
//        root.right.left = new TreeNode(0);
//        root.right.right = new TreeNode(8);
        TreeNode t1 = new TreeNode(1);
        t1.left = new TreeNode(2);
        t1.right = new TreeNode(3);

        TreeNode t2 = new TreeNode(2);
        System.out.println(checkSubTree(t1, t2));

    }

    public static boolean checkSubTree(TreeNode t1, TreeNode t2) {
        //前序
        qianxu(t1, t2);//找到与t2头结点一样的结点
        return p;
    }

    public static void qianxu(TreeNode t1, TreeNode t2) {
        if (t1 == null) {
            return;
        }
        System.out.println(t1.val);
        if (t1.val == t2.val) {
            nowP = true;
            search(t1, t2);
            p |= nowP;
        }
        if (p) {
            return;
        }
        checkSubTree(t1.left, t2);
        checkSubTree(t1.right, t2);
    }

    public static void search(TreeNode t1, TreeNode t2) {
        if (t2 == null) {
            return;
        }
        if (t1 == null) {
            nowP = false;
        }
        if (t1.val != t2.val) {
            nowP = false;
        }
        if (nowP) {
            search(t1.left, t2.left);
            search(t1.right, t2.right);
        }
    }

    public boolean checkSubTree2(TreeNode t1, TreeNode t2) {
        if(t1 == null && t2 == null)
            return true;
        if(t1 == null || t2 == null)
            return false;

        return t1.val == t2.val && checkSubTree(t1.left, t2.left) && checkSubTree(t1.right, t2.right) || checkSubTree(t1.right, t2) || checkSubTree(t1.left, t2);
    }
}
